// *******************************************************************
// >> File Name: /home/diabio/project/al_cache/al_cache/arc_cache/arc_lfu_part.h
// >> Author: diabiolin
// >> Created Time: Fri 25 Apr 2025 10:50:05 PM CST
// >> Description:
// *******************************************************************
#pragma once 

#include "arc_cache_node.h"
#include <unordered_map>
#include <map>
// #include <mutex>
#include <list>

namespace al_cache{

template <typename Key, typename Value>
class ArcLfuPart{

public:
	using NodeType = ArcNode<Key, Value>;
	using NodePtr = std::shared_ptr<NodeType>;
	using NodeMap = std::unordered_map<Key, NodePtr>;
	using FreqMap = std::map<size_t, std::list<NodePtr>>;

	explicit ArcLfuPart(size_t capacity, size_t transformThreshold)
		: capacity_(capacity)
		, ghostCapacity_(capacity)
		, transformThreshold_(transformThreshold)
		, minFreq_(0)
		{
			initializeList();
		}

	bool put(Key key, Value value){
		if(capacity_ == 0){
			return false;
		}
		// std::lock_guard<std::mutex> lock(mutex_);
		auto it = mainCacheMap_.find(key);
		if(it != mainCacheMap_.end()){
			return updateExitingNode(it->second, value);
		}
		return addNewNode(key, value);
	}

	bool get(Key key, Value& value){
		// std::lock_guard<std::mutex> lock(mutex_);
		auto it = mainCacheMap_.find(key);
		if(it != mainCacheMap_.end()){
			updateNodeFrequency(it->second);
			value = it->second->getValue();
			return true;
		}
		return false;
	}

	bool checkGhost(Key key){
		// std::lock_guard<std::mutex> lock(mutex_);
		auto it = ghostCacheMap_.find(key);
		if(it != ghostCacheMap_.end()){
			// 先保存 node 的 shared_ptr，确保 removeFromGhost 时 node 还活着
			NodePtr node = it->second;
			removeFromGhost(node);
			ghostCacheMap_.erase(it);
			// 之后不能再访问 node
			return true;
		}
		return false;
	}

	void increaseCapacity(){
		capacity_++;
	}

	bool decreaseCapacity(){
		if(capacity_ <= 0){
			return false;
		}
		if(mainCacheMap_.size() == capacity_){
			evictLeastFrequent();
		}
		capacity_--;
		return true;
	}

private:
	size_t capacity_;
	size_t ghostCapacity_;
	size_t transformThreshold_;
	size_t minFreq_;
	// std::mutex mutex_;

	NodeMap mainCacheMap_;
	NodeMap ghostCacheMap_;
	FreqMap freMap_;

	NodePtr ghostHead_;
	NodePtr ghostTail_;

	// 一些私有方法
	void initializeList(){
		ghostHead_ = std::make_shared<NodeType>();
		ghostTail_ = std::make_shared<NodeType>();
		ghostHead_->next_ = ghostTail_;
		ghostTail_->prev_ = ghostHead_;
	}

	bool updateExitingNode(NodePtr node, const Value& value){
		node->setValue(value);
		updateNodeFrequency(node);
		return true;
	}

	bool addNewNode(const Key& key, const Value& value){
		if(mainCacheMap_.size() >= capacity_){
			evictLeastFrequent();
		}

		NodePtr newNode = std::make_shared<NodeType>(key, value);
		mainCacheMap_[key] = newNode;

		if(freMap_.find(1) == freMap_.end()){
			freMap_[1] = std::list<NodePtr>();
		}
		freMap_[1].push_back(newNode);
		minFreq_ = 1;

		return true;
	}

	void updateNodeFrequency(NodePtr node){
		size_t oldFreq = node->getAccessCount();
		node->incrementAccessCount();
		size_t newFreq = node->getAccessCount();

		auto& oldList = freMap_[oldFreq];
		oldList.remove(node);
		if(oldList.empty()){
			freMap_.erase(oldFreq);
			if(oldFreq == minFreq_){
				minFreq_ = newFreq;
			}
		}

		if(freMap_.find(newFreq) == freMap_.end()){
			freMap_[newFreq] = std::list<NodePtr>();
		}
		freMap_[newFreq].push_back(node);
	}

	void evictLeastFrequent(){
		if(freMap_.empty()){
			return;
		}

		auto& minFreqList = freMap_[minFreq_];
		if(minFreqList.empty()){
			return;
		}

		NodePtr leastNode = minFreqList.front();
		minFreqList.pop_front();

		if(minFreqList.empty()){
			freMap_.erase(minFreq_);
			if(!freMap_.empty()){
				minFreq_ = freMap_.begin()->first;
			}
		}

		if(ghostCacheMap_.size() >= ghostCapacity_){
			removeOldestGhost();
		}
		addToGhost(leastNode);

		mainCacheMap_.erase(leastNode->getKey());
	}

	void removeFromGhost(NodePtr node){
		if (!node) return;
		// 显式保存 prev/next，保证断链时它们还活着
		auto prev = node->prev_.lock();
		auto next = node->next_;
		if (prev) prev->next_ = next;
		if (next) next->prev_ = node->prev_;
		node->prev_.reset();
		node->next_ = nullptr;
	}
	
	void addToGhost(NodePtr node){
		node->next_ = ghostTail_;
		node->prev_ = ghostTail_->prev_;
		if(auto prev = ghostTail_->prev_.lock()){
			prev->next_ = node;
		}
		// ghostTail_->prev_->next_ = node;
		ghostTail_->prev_ = node;
		ghostCacheMap_[node->getKey()] = node;
	}

	void removeOldestGhost() {
		NodePtr oldestGhost = ghostTail_->prev_.lock();
		if (oldestGhost && oldestGhost != ghostHead_) {
			removeFromGhost(oldestGhost);
			ghostCacheMap_.erase(oldestGhost->getKey());
		}
	}
};

}// namespace al_cache

